あなたのミッション 🎯
2次元座標で与えられた $N$ 個の惑星を、最小コストの「ハイパーレーン」ネットワークで再接続してください。
- 目標：すべての $N$ 個の惑星（頂点）を接続し、すべてが直接または間接的に到達可能になるようにします。
- 目的：**総コスト**を最小にするネットワーク設計を見つけます。
解析 🛰️
レーン（辺）のコストは、ユークリッド距離です：
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- レーンは、任意の2つの惑星の間に建設できます。
- つまり、私たちは完全（密集）グラフを持っています。
解法 ⚙️
これは古典的な最小全域木（MST）問題です。
- アルゴリズム：ヒントではプリム法（$O(V^2)$版）を推奨しています。これは密集したグラフに最適です。
- 開始点：アルゴリズムは惑星0から始めて、一貫した結果を得ます。
完全グラフ（左）はすべての可能な辺を持ちます。最小全域木（右）は、すべての頂点を接続する最も安価な辺の部分集合です。